/**
 * 剑指 Offer 53 - I. 在排序数组中查找数字 I
 * https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let index = -1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    if (nums[middle] === target) {
      index = middle;
      break;
    }
    if (nums[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  if (index < 0) {
    return 0;
  }
  let begin = index - 1;
  while (begin >= 0 && nums[begin] === target) {
    begin -= 1;
  }
  let end = index + 1;
  while (end < nums.length && nums[end] === target) {
    end += 1;
  }
  return end - begin - 1;
}

console.log(search([5, 7, 7, 8, 8, 10], 8) === 2);
console.log(search([5, 7, 7, 8, 8, 10], 6) === 0);
